Usenet 1993 July/InfoMagic USENET CD-ROM July 1993.ISO/sources/unix/volume24/yabbawhap/part03

Internet Message Format | 1991-10-09 | 54.1 KB

Subject:  v24i075:  Public-domain replacement for compress programs, Part03/04
Newsgroups: comp.sources.unix
Approved: [e-mail]
X-Checksum-Snefru: db10e3bf d4d49c41 27b2b1fb b1ebd740

Submitted-by: Dan Bernstein <[e-mail]>
Posting-number: Volume 24, Issue 75
Archive-name: yabbawhap/part03

#! /bin/sh
# This is a shell archive.  Remove anything before this line, then feed it
# into a shell via "sh file" or similar.  To overwrite existing files,
# type "sh file -c".
# The tool that generated this appeared in the comp.sources.unix newsgroup;
# send mail to [e-mail] if you want that tool.
# Contents:  BLURB CHANGES INSTALL PATENTS QUESTIONS bitout.c huptrie.h
#   percent.c sysconf texts.c unwhap.c unyabba.1 yabba.1
# Wrapped by [e-mail] on Wed Mar 20 17:09:24 1991
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
echo If this archive is complete, you will see the following message:
echo '          "shar: End of archive 3 (of 4)."'
if test -f 'BLURB' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'BLURB'\"
else
  echo shar: Extracting \"'BLURB'\" \(1000 characters\)
  sed "s/^X//" >'BLURB' <<'END_OF_FILE'
XThis package includes yabba and unyabba, portable implementations of Y
Xcoding. Y coding is unpatented---unlike the LZW coding used by compress
Xand the LZ78 variants used by most other dictionary compressors. Y also
Xgives somewhat better compression than LZW.
X
XAs an extra bonus, this package also includes whap and unwhap, portable
Ximplementations of AP coding. AP coding is patented, but like Y it is
Xmore effective than LZW. whap runs about as fast as compress and, in its
Xdefault configuration, uses less memory; unwhap runs as fast as
Xuncompress and uses less than half as much memory.
X
XThe entire package is public-domain. You can copy my Y code into any
Xapplication without fear of copyrights or patents. Be aware, however,
Xthat the current implementation is probably not too close to optimal,
Xand I am actively searching for a better method. If AP were not patented
XI would recommend that you use it instead. For more information see
XPATENTS in the package.
X
X---Dan Bernstein, [e-mail]
END_OF_FILE
  if test 1000 -ne `wc -c <'BLURB'`; then
    echo shar: \"'BLURB'\" unpacked with wrong size!
  fi
  # end of 'BLURB'
fi
if test -f 'CHANGES' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'CHANGES'\"
else
  echo shar: Extracting \"'CHANGES'\" \(2782 characters\)
  sed "s/^X//" >'CHANGES' <<'END_OF_FILE'
Xyabbawhap change file, in reverse chronological order
X
XEF is Eirik Fuller <[e-mail]>.
XDG is Dave Gudeman <[e-mail]>.
XMA is Marc Andreessen <[e-mail]>.
XLR is Loren J. Rittle <[e-mail]>.
XCP is Colin Plumb <[e-mail]>.
XFW is Frank Wales <[e-mail]>.
XGT is Graham Thoal <[e-mail]>.
X
X3/19/91: yabbawhap 1.00.
X3/19/91: Cleaned up for 1.00 release. Hopefully no further changes.
X3/19/91: Changed >> 4 to / 16 to handle longs. Tnx GT.
X3/19/91: Added ycoding.4b, latest revision of paper.
X3/19/91: No major changes in a while, release seems appropriate.
X
X3/14/91: Fixed up various other %d and %ld's. Tnx GT.
X3/14/91: Changed %d to %ld for per. Tnx GT.
X3/14/91: Fixed 9999% to 9999%%. (Will this ever matter?) Tnx GT.
X
X3/13/91: Had OPTCANT2 and OPTCANT1 affect DOWNI. I don't like this...
X3/13/91: Replaced DOWN2 with DOWNI (``down inner'') in yw.c, unyabba.c.
X3/13/91: Added -s to ls in try, tryap.
X3/13/91: Noted try* changes in README.
X3/13/91: Removed -L from ls's in try*. Tnx FW.
X3/13/91: Removed test -s stuff from try*. csh's too incompatible. Tnx FW.
X3/13/91: Changed .memset.$$.* to .mmset.$$.* in sysconf. Tnx FW.
X3/13/91: Added space before comment line 25 huptrie.h. Tnx FW.
X     Microsoft SCO compiler reports error on int */*comment*/. Dorks.
X
X3/6/91: yabbawhap 0.981.
X3/6/91: Took out test code from yw.c. Aargh.
X
X3/6/91: yabbawhap 0.98.
X3/6/91: Fixed up .h dependencies in Makefile.
X
X2/27/91: Added HASHPTRS to huptrie.h. Only visible change is tophash().
X2/27/91: Fixed up ADDAVAIL, INIT, and extra hc parens, just in case. Tnx CP.
X2/27/91: Noted in Makefile and QUESTIONS that HASHTYPE does affect memory.
X2/27/91: Changed initial ADDs in yw.c to use curhash as a temporary.
X2/25/91: Added QUESTIONS.
X
X2/20/91: Fixed unsigned long return in percent.c. Tnx LR.
X2/20/91: Fixed goaheadandbeverbose() and initrandom() to void returns. Tnx LR.
X2/20/91: Changed unwhap logic slightly.
X2/19/91: Changed sysconf to automatically run checkconf if the user wants.
X2/19/91: Added warning in README about ZEROFILLED.
X2/19/91: Added warning in README about changing -m. Tnx DG.
X2/19/91: Changed to -UZEROFILLED as the default; sysconf sets -DZEROFILLED.
X2/19/91: Changed whap to unwhap in unyabba man page. Tnx MA.
X2/19/91: Changed tryap and tryapy to interact better with whapwarning. Tnx DG.
X2/19/91: Fixed up non-use of BRAINDAMAGED in un*.
X2/19/91: Added DOWN1, DOWN0, OPTCANT2, OPTCANT1.
X2/18/91: Changed BRAINDAMAGED test slightly for Utek and similar. Tnx EF.
X2/18/91: Fixed up sysconf's BRAINDAMAGED test. Oops. Tnx EF.
X2/18/91: Added notice about checkconf to the end of sysconf.
X2/18/91: Changed sysconf to use cat << instead of echo. I hate System V.
X
X2/17/91: yabbawhap 0.95.
END_OF_FILE
  if test 2782 -ne `wc -c <'CHANGES'`; then
    echo shar: \"'CHANGES'\" unpacked with wrong size!
  fi
  # end of 'CHANGES'
fi
if test -f 'INSTALL' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'INSTALL'\"
else
  echo shar: Extracting \"'INSTALL'\" \(1302 characters\)
  sed "s/^X//" >'INSTALL' <<'END_OF_FILE'
X#!/bin/sh
X# Public domain.
X
XMODE=0755
X
XYABBA=/usr/local/bin/yabba
XUNYABBA=/usr/local/bin/unyabba
XWHAP=/usr/local/bin/whap
XUNWHAP=/usr/local/bin/unwhap
X
XMYABBA=/usr/man/man1/yabba.1
XMUNYABBA=/usr/man/man1/unyabba.1
X
Xecho "Each action will be printed before it is run. Press return to proceed."
Xecho "Note that you need a BSD-compatible install program or script."
X
Xecho "1. Install yabba and unyabba."
Xecho "! install -c -m $MODE yabba $YABBA: " | tr -d '\012'
Xread line
Xinstall -c -m "$MODE" yabba "$YABBA"
X
Xecho "! install -c -m $MODE unyabba $UNYABBA: " | tr -d '\012'
Xread line
Xinstall -c -m "$MODE" unyabba "$UNYABBA"
X
Xecho "2. Install whap and unwhap."
Xif test -r whap -a -r unwhap
Xthen echo "! install -c -m $MODE whap $WHAP: " | tr -d '\012'
X     read line
X     install -c -m "$MODE" whap "$WHAP"
X
X     echo "! install -c -m $MODE unwhap $UNWHAP: " | tr -d '\012'
X     read line
X     install -c -m "$MODE" unwhap "$UNWHAP"
X
Xelse echo "Looks like you don't have whap compiled. Fine, let's continue."
Xfi
X
Xecho "3. Make the man pages available."
Xecho "! install -c -m 0444 yabba.1 $MYABBA: " | tr -d '\012'
Xread line
Xinstall -c -m 0444 yabba.1 "$MYABBA"
X
Xecho "! install -c -m 0444 unyabba.1 $MUNYABBA: " | tr -d '\012'
Xread line
Xinstall -c -m 0444 unyabba.1 "$MUNYABBA"
X
Xecho "That's it!"
X
Xexit 0
END_OF_FILE
  if test 1302 -ne `wc -c <'INSTALL'`; then
    echo shar: \"'INSTALL'\" unpacked with wrong size!
  fi
  chmod +x 'INSTALL'
  # end of 'INSTALL'
fi
if test -f 'PATENTS' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'PATENTS'\"
else
  echo shar: Extracting \"'PATENTS'\" \(4266 characters\)
  sed "s/^X//" >'PATENTS' <<'END_OF_FILE'
XAfter someone patents a product or method that he invented, he can sue
Xanyone who makes, uses, or sells the invention. You've probably heard
Xthat Welch at Unisys patented LZW compression some years back, and so
XUnisys can sue anyone who uses UNIX compress or any similar program.
XYou may not have heard that Miller and Wegman at IBM independently
Xdiscovered several compression methods, including LZW---and sent their
Xpatent application to the Patent & Trademark Office before Welch did.
XSo it appears that IBM controls LZW.
X
XHow can Unisys patent something that IBM already patented? And how can
Xeither of them patent what are obviously mathematical algorithms, when
Xmathematical algorithms aren't supposed to be patentable? The answer is
Xthat the Patent & Trademark Office doesn't let mathematicians and
Xcomputer scientists become patent examiners. So none of their examiners
Xcan recognize mathematics without a court order, and even then they have
Xtrouble. They also can't tell that two patents cover exactly the same
Xalgorithm when the wording is slightly different.
X
XPractically every good compression method in the last ten years has been
Xpatented. Modem and disk manufacturers can't ignore the possibility of
Xgovernment-approved monopolies on compressors: there's too much money at
Xstake. So they apply for one patent after another, twisting the wording
Xas much as possible so that the patent examiners don't realize they're
Xpatenting mathematics. By and large, they succeed.
X
XOn December 26, 1990, I discovered an apparently new compression method,
XY coding. I haven't found a way to make Y run as fast as compress (yet),
Xbut it's not too slow for general use, and it produces better results
Xoverall than any other non-Huffman dictionary compressor I've seen. I am
Xsick and tired of having to tiptoe through this minefield of patents; I
Xwant a method that produces good results and can be used freely by
Xanyone. Well, now I have it. Everything in Y coding is public domain. No
Xcopyrights, no patents, no protection at all, on the code or on the
Xalgorithms or on the file format or on anything else. I can't be totally
Xsure, of course, that I'm the first to discover Y, but everyone I've
Xtalked to thinks it's new. Use it as you will.
X
XSeveral months before I found Y coding, I found what I now know to be
XStorer's AP coding. At first I thought it was new, and I started putting
Xtogether an implementation. It's quite a bit faster than my Y
Ximplementation---even faster than compress on some machines---and uses
Xless memory. But it has turned out to be patented. I've included the
Xcode in my Y package because I don't want my work to go to waste, but it
Xcan't be used freely. You can use AP for what's sometimes called
X``experimental use''; the precise wording in most court cases is ``for
Xthe sole purpose of satisfying philosophical taste or curiosity, or for
Xinstruction and amusement.'' Patents never apply to that sort of use.
X
XIf you like AP's efficiency and want to start using it for more than
Xsatisfying your philosophical curiosity, you might be tempted to ask
XStorer for a license. Don't give in! First, his patent---any compression
Xpatent---is on very shaky ground, and as it hasn't been acknowledged in
Xthe industry, it's even weaker. Second, you can challenge the patent by
Xsending the Patent & Trademark Office about $2000 and an explanation of
Xwhy AP is a mathematical algorithm. Now you may not have the money or
Xlawyers or time or energy to do this successfully, but there are a lot
Xof people who feel just as restricted. You should check up on the League
Xfor Programming Freedom; if you don't subscribe to their political goals
Xbut still want to get rid of compression patents, send me a note. In any
Xcase this will be cheaper on everyone than paying Storer for something
Xhe shouldn't even control. Third, Y isn't that much slower than AP, and
Xit compresses just as effectively. Chances are good that I or someone
Xelse will find a faster implementation soon. Finally, we may be able to
Xconvince Storer to donate his patent to the public good. If you want to
Xappeal to his morals, send a note to [e-mail], copy to
[e-mail].
X
XDisclaimer: I'm not a lawyer. I'm just an outraged citizen.
X
X---Dan Bernstein, [e-mail]
END_OF_FILE
  if test 4266 -ne `wc -c <'PATENTS'`; then
    echo shar: \"'PATENTS'\" unpacked with wrong size!
  fi
  # end of 'PATENTS'
fi
if test -f 'QUESTIONS' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'QUESTIONS'\"
else
  echo shar: Extracting \"'QUESTIONS'\" \(3130 characters\)
  sed "s/^X//" >'QUESTIONS' <<'END_OF_FILE'
X1. Aack! It won't compile! It doesn't work! What do I do?
X2. Why do yabba and whap use so much memory?
X3. Why does squeeze do better than yabba and whap on long files?
X4. What does ``block size'' mean?
X5. Why doesn't yabba take a filename argument?
X6. When will there be a new version of yabbawhap?
X
X
X1. Aack! It won't compile! It doesn't work! What do I do?
X
XRead through README, Makefile, and QUESTIONS. Make checkconf, run it,
Xand read carefully through its output. Then try again. If you still have
Xtrouble, send the author a note at [e-mail].
X
X
X2. Why do yabba and whap use so much memory?
X
XWith -UPTRS -DTYPE=short you will typically use half as much memory on a
X32-bit machine. With -DHASHTYPE=short you will save some more memory for
Xyabba and unyabba, though not for whap or unwhap. These changes usually
Xcost a bit of speed. See Makefile for more details.
X
XYou can also change the block size by changing NODEMAX and MOD. These
Xdon't really affect speed, but they do affect compression. With them you
Xcan make yabba and whap use as much or as little memory as you like.
X
X
X3. Why does squeeze do better than yabba and whap on long files?
X
XBy default, yabba and whap are compiled to use similar amounts of memory
Xto compress. squeeze uses a lot more memory, so it can keep track of
Xmore patterns in the input. If you compile yabba and whap with NODEMAX
Xand MOD so high that they use as much memory, they'll do better than
Xsqueeze.
X
XFor example, on a 97338-byte shell archive, yabba -m65533 compresses to
X39266 bytes, and whap -m65533 compresses to 37358 bytes. yabba -m100000
Xcompresses to 36673 bytes, and whap -m100000 compresses to 33566 bytes.
X(In contrast, compress produces 43322 bytes, squeeze produces 33943
Xbytes, and lharc produces 32455 bytes. A Huffman coder layered on top of
Xyabba or whap would produce even better results.)
X
XThere are occasional files where squeeze performs better than yabba and
Xwhap no matter how much memory you use, but never by much.
X
X
X4. What does ``block size'' mean?
X
XThe number after -m represents a number of input characters. -m100000
Xmeans that yabba (or whap) will try to find patterns in a stretch of
Xinput up to 100000 characters long. NODEMAX and NODENUM are on the same
Xscale. Here 100000 is the block size. In the above example with a
X97338-byte file, any -m value above 97338 will produce the same results.
X
X(For compress, the natural block size is the number of patterns it is
Xkeeping track of at once, not the number of input characters. With -b14,
Xcompress will keep track of 2^14 or 16384 patterns at once. Typically
X16384 patterns would stretch over 60000 input characters. -b16 is
Xroughly equivalent to -m300000.)
X
X
X5. Why doesn't yabba take a filename argument?
X
XWait for the -f option. Separate programs, fyabba and funyabba, will
Xapply yabba and unyabba to files; fyabbadir and funyabbadir will work on
Xdirectory hierarchies.
X
X
X6. When will there be a new version of yabbawhap?
X
XI am actively working on the next release; I have targeted version 1.50
Xwith most of the planned extensions for May 1. Send any suggestions or
Xpatches to me at [e-mail].
END_OF_FILE
  if test 3130 -ne `wc -c <'QUESTIONS'`; then
    echo shar: \"'QUESTIONS'\" unpacked with wrong size!
  fi
  # end of 'QUESTIONS'
fi
if test -f 'bitout.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'bitout.c'\"
else
  echo shar: Extracting \"'bitout.c'\" \(2064 characters\)
  sed "s/^X//" >'bitout.c' <<'END_OF_FILE'
X/* Placed into the public domain by Daniel J. Bernstein. */
X
X#include <stdio.h>
X#include "bitout.h"
X
Xstatic int twom1[9] = { 0,1,3,7,15,31,63,127,255 } ;
X
Xbitword bit_wbuf[BITBUFSIZE + 1];
Xbitnum bit_bbuf[BITBUFSIZE + 1];
Xint bit_bufsize = 0;
X
Xlong bit_numout = 0;
X
Xstatic int savecurbyte = 0;
Xstatic bitnum savecurbb8 = 8;
X
Xint bit_printbuf()
X{
X register int curbyte = savecurbyte;
X register bitnum curbb8 = savecurbb8;
X register bitword curw;
X register int i;
X
X /* XXX: should use registers & curbyte & so on better */
X
X for (i = 0;i < bit_bufsize;i++)
X  {
X   /* assumes bit_bbuf[i] <= 0 */
X   curw = bit_wbuf[i];
X   curbyte += ((curw & twom1[curbb8]) << (8 - curbb8));
X#ifdef BRAINDAMAGED
X   if (curbyte == 255)
X     (void) putchar((char) curbyte);
X   else
X#endif
X   if (putchar((char) curbyte) == EOF)
X     return EOF;
X   bit_numout++;
X   curw >>= curbb8;
X   curbb8 += bit_bbuf[i];
X
X   /* just in case bit_bbuf[i] < -7 */
X   while (curbb8 <= 0)
X    {
X#ifdef BRAINDAMAGED
X     if (curw & 255 == 255)
X       (void) putchar((char) (curw & 255));
X     else
X#endif
X     if (putchar((char) (curw & 255)) == EOF)
X       return EOF;
X     bit_numout++;
X     curbb8 += 8;
X     curw >>= 8;
X    }
X   curbyte = (int) curw; /* does not lose accuracy */
X  }
X savecurbyte = curbyte; /* ah, the joy of coroutines */
X savecurbb8 = curbb8; /* better this way (double vars) for efficiency */
X bit_bufsize = 0;
X return 0;
X}
X
Xint bit_flushbuf()
X{
X if (bit_printbuf() == EOF)
X   return EOF;
X if (savecurbb8 < 8)
X  {
X#ifdef BRAINDAMAGED
X   if (savecurbyte == 255)
X     (void) putchar((char) savecurbyte);
X   else
X#endif
X   if (putchar((char) savecurbyte) == EOF)
X     return EOF;
X   bit_numout++;
X  }
X savecurbyte = 0;
X savecurbb8 = 8;
X return 0;
X}
X
Xint bit_fillflush(x)
Xint x;
X{
X if (bit_printbuf() == EOF)
X   return EOF;
X savecurbyte += (x << 8 - savecurbb8) & 255;
X#ifdef BRAINDAMAGED
X if (savecurbyte == 255)
X   (void) putchar((char) savecurbyte);
X else
X#endif
X if (putchar((char) savecurbyte) == EOF)
X   return EOF;
X bit_numout++;
X savecurbyte = 0;
X savecurbb8 = 8;
X return 0;
X}
END_OF_FILE
  if test 2064 -ne `wc -c <'bitout.c'`; then
    echo shar: \"'bitout.c'\" unpacked with wrong size!
  fi
  # end of 'bitout.c'
fi
if test -f 'huptrie.h' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'huptrie.h'\"
else
  echo shar: Extracting \"'huptrie.h'\" \(7295 characters\)
  sed "s/^X//" >'huptrie.h' <<'END_OF_FILE'
X/* Placed into the public domain by Daniel J. Bernstein. */
X
X#ifndef HUPTRIE_H
X#define HUPTRIE_H
X
X/* Ever seen an efficient data structure library? You're about to. */
X
X/* Yes, folks, I have some documentation for this; I'm just not sure */
X/* that the library is ready for general release yet. If you're */
X/* desperate for huptries in an application and *need* to use this */
X/* library *now*, let me know. */
X
X/*#defines: PTRS, TYPE, HASHTYPE, ZEROFILLED, BZERO, MEMZERO, OPTCANT{1,2,5}.*/
X/* HASHPTRS. */
X
X#ifndef HASHTYPE
X#define HASHTYPE TYPE
X#endif
X
Xtypedef unsigned TYPE pos;
X
X#ifdef PTRS
Xtypedef struct nod { struct nod *p; struct nod *n; } *node;
Xtypedef struct nod *next;
Xtypedef int * /*XXX: irrelevant*/ parent;
X#else
Xtypedef pos node;
Xtypedef node *next;
Xtypedef node *parent;
X#endif
X
X#ifdef HASHPTRS
Xtypedef struct hod { node n; struct hod *h; } htt;
Xtypedef struct hod *hash;
X#define HASHP 255
X#define HANO(h,sh) ((sh)->n)
X#else
Xtypedef node htt;
Xtypedef unsigned HASHTYPE hash;
X#define HASHP 0
X#define HANO(h,sh) ((h)[sh])
X#endif
X
Xtypedef htt *hashtable;
Xtypedef pos ipos;
X
X/* A huptrie consists of:
X   next n; parent p; hashtable h;
X   ipos m; pos sm; pos l1; hash h1;
X*/
X
X#define TOPHASH 5381
X
X#ifdef HASHPTRS
X#define hh(sh,sch,h1) (please do not use this yet, XXX)
X#define hc(sh,c,h1) (sh[(unsigned char) c].h)
X#else
X#define hh(sh,sch,h1) (((sch) - (((sh) << 5) + (sh))) & (h1))
X#define hc(sh,c,h1) ((((sh) << 5) + (sh) + ((hash) (unsigned char) (c))) & (h1))
X#endif
X
X#ifdef PTRS
X#define NEXT(ne,no) ((no)->n)
X#define PARENT(pa,no) ((no)->p)
X#define AVAIL(ne) ((ne)[0].n)
X#define NODEBYN(ne,po) ((ne) + (po))
X#else
X#define NEXT(ne,no) ((ne)[no])
X#define PARENT(pa,no) ((pa)[no])
X#define AVAIL(ne) ((ne)[0])
X#define NODEBYN(ne,po) (po)
X#endif
X
X/* INIT, HUP_DELETE, DOWN are block statements. */
X
X/* n,p,h,m,sm are by address */
X#ifdef PTRS
X#define INIT(n,p,h,m,sm,l1,h1) \
X{ (n) = malloc(sizeof(struct nod) * ((l1) + 1)); AVAIL(n) = 0; \
X (h) = (hashtable) malloc(sizeof(htt) * ((h1) + HASHP + 1)); \
X CLEARHASH(h,h1); FIRSTHASH(h,h1); (m) = (l1) + 1; (sm) = -1; }
X#define STATICDECLARE(n,p,h,l1,h1) \
X  struct nod (n)[(l1) + 1]; parent (p); htt (h)[(h1) + HASHP + 1];
X#else
X#define INIT(n,p,h,m,sm,l1,h1) \
X{ (n) = (next) malloc(sizeof(node) * ((l1) + 1)); AVAIL(n) = 0; \
X (p) = (parent) malloc(sizeof(node) * ((l1) + 1)); \
X (h) = (hashtable) malloc(sizeof(htt) * ((h1) + HASHP + 1)); \
X CLEARHASH(h,h1); FIRSTHASH(h,h1); (m) = (l1) + 1; (sm) = -1; }
X#define STATICDECLARE(n,p,h,l1,h1) \
X  node (n)[(l1) + 1]; node (p)[(l1) + 1]; htt (h)[(h1) + HASHP + 1];
X#endif
X
X#define STATICINIT(n,p,h,m,sm,l1,h1) \
X{ INITHASH(h,h1); AVAIL(n) = 0; (m) = (l1) + 1; (sm) = -1; }
X/* FIRSTHASH(h,h1)  XXX*/
X
X#ifdef HASHPTRS
X#define FIRSTHASH(h,h1) { hash ha; ha = (h) + ((h1) + HASHP + 1); \
Xdo { --ha; ha->h = (h) + ((((ha - h) << 5) + (ha - h)) & (h1)); } \
Xwhile (ha != (h)); }
X#else
X#define FIRSTHASH(h,h1) ;
X#endif
X
X#ifdef ZEROFILLED
X#define INITHASH(h,h1) ;
X#else
X#define INITHASH(h,h1) CLEARHASH(h,h1);
X#endif
X
X#ifdef HASHPTRS
X#define CLEARHASH(h,h1) { hash ha; ha = (h) + ((h1) + 1); do HANO(h,--ha) = 0; while (ha != (h)); }
X/* XXX: if -UZEROFILLED, this is unnecessarily inefficient on the first CLEARHASH */
X#else
X#ifdef BZERO
X#define CLEARHASH(h,h1) (void) bzero((char *) (h),sizeof(node) * ((h1) + 1));
X#else
X#ifdef MEMZERO
X#define CLEARHASH(h,h1) (void) memset((char *) (h),0,sizeof(node) * ((h1) + 1));
X#else
X#define CLEARHASH(h,h1) { hash ha; ha = (h1) + 1; do HANO(h,--ha) = 0; while (ha); }
X#endif
X#endif
X#endif
X
X
X/* sm and newnode are by address */
X#define ADDAVAIL(n,p,h,sm,sp,sch,newnode) \
X( --(sm), (newnode = AVAIL(n)), (AVAIL(n) = NEXT(n,newnode)), \
X (PARENT(p,newnode) = (sp)), \
X (NEXT(n,newnode) = HANO(h,sch)), (HANO(h,sch) = (newnode)) )
X
X/* m, sm, newnode are by address */
X#define WASTEMAX(n,p,h,m,sm,newnode) \
X( (++(sm)), (newnode = NODEBYN(n,--(m))), (PARENT(p,newnode) = 0), \
X (NEXT(n,newnode) = AVAIL(n)), (AVAIL(n) = (newnode)) )
X
X/* m and newnode are by address */
X#define ADDMAX(n,p,h,m,sp,sch,newnode) \
X( (newnode = NODEBYN(n,--(m))), (PARENT(p,newnode) = (sp)), \
X (NEXT(n,newnode) = HANO(h,sch)), (HANO(h,sch) = (newnode)) )
X
X/* sm and noptr are by address */
X#define HUP_DELETE(n,p,h,sm,sp,sh,noptr) \
X{ (noptr) = &(HANO(h,sh)); while (*(noptr) != (sp)) (noptr) = &(NEXT(n,*(noptr))); \
X *(noptr) = NEXT(n,sp); PARENT(p,sp) = 0; NEXT(n,sp) = AVAIL(n); \
X AVAIL(n) = (sp); ++(sm); }
X
X/* no is by address, FOUND and NOTFOUND are formal */
X/* XXX: Reorganize hash lists? */
X#define DOWN2(n,p,h,sp,sch,no,FOUND,NOTFOUND) { \
X if ((no) = HANO(h,sch)) { if (PARENT(p,no) != (sp)) { \
X if ((no) = NEXT(n,no))  { if (PARENT(p,no) != (sp)) { \
X if ((no) = NEXT(n,no))  { if (PARENT(p,no) != (sp)) { \
X   do (no) = NEXT(n,no); while ((no) && (PARENT(p,no) != (sp))); \
X   if (no) { FOUND } else { NOTFOUND } \
X } else { FOUND } } else { NOTFOUND } \
X } else { FOUND } } else { NOTFOUND } \
X } else { FOUND } } else { NOTFOUND } \
X}
X
X#define DOWN1(n,p,h,sp,sch,no,FOUND,NOTFOUND) { \
X if ((no) = HANO(h,sch)) { if (PARENT(p,no) != (sp)) { \
X if ((no) = NEXT(n,no))  { if (PARENT(p,no) != (sp)) { \
X   do (no) = NEXT(n,no); while ((no) && (PARENT(p,no) != (sp))); \
X   if (no) { FOUND } else { NOTFOUND } \
X } else { FOUND } } else { NOTFOUND } \
X } else { FOUND } } else { NOTFOUND } \
X}
X
X#define DOWN0(n,p,h,sp,sch,no,FOUND,NOTFOUND) { \
X if ((no) = HANO(h,sch)) { if (PARENT(p,no) != (sp)) { \
X   do (no) = NEXT(n,no); while ((no) && (PARENT(p,no) != (sp))); \
X   if (no) { FOUND } else { NOTFOUND } \
X } else { FOUND } } else { NOTFOUND } \
X}
X
X#define DOWN5(n,p,h,sp,sch,no,FOUND,NOTFOUND) { \
X if ((no) = HANO(h,sch)) { if (PARENT(p,no) != (sp)) { \
X if ((no) = NEXT(n,no))  { if (PARENT(p,no) != (sp)) { \
X if ((no) = NEXT(n,no))  { if (PARENT(p,no) != (sp)) { \
X if ((no) = NEXT(n,no))  { if (PARENT(p,no) != (sp)) { \
X if ((no) = NEXT(n,no))  { if (PARENT(p,no) != (sp)) { \
X if ((no) = NEXT(n,no))  { if (PARENT(p,no) != (sp)) { \
X   do (no) = NEXT(n,no); while ((no) && (PARENT(p,no) != (sp))); \
X   if (no) { FOUND } else { NOTFOUND } \
X } else { FOUND } } else { NOTFOUND } \
X } else { FOUND } } else { NOTFOUND } \
X } else { FOUND } } else { NOTFOUND } \
X } else { FOUND } } else { NOTFOUND } \
X } else { FOUND } } else { NOTFOUND } \
X } else { FOUND } } else { NOTFOUND } \
X}
X
X#ifdef OPTCANT1
X#define DOWN DOWN0
X#define DOWNI DOWN0
X#else
X#ifdef OPTCANT2
X#define DOWN DOWN1
X#define DOWNI DOWN1
X#else
X#ifdef OPTCANT5
X#define DOWN DOWN2
X#define DOWNI DOWN2
X#else
X#define DOWN DOWN5
X#define DOWNI DOWN2
X#endif
X#endif
X#endif
X
X#define hup_parent(p,no) PARENT(p,no)
X#define setparent(p,scp,sp) (PARENT(p,scp) = (sp))
X#ifdef HASHPTRS
X#define tophash(h,h1) ((h) + (TOPHASH & (h1)))
X#else
X#define tophash(h,h1) (TOPHASH & (h1))
X#endif
X#define topnode(n,l1) (NODEBYN(n,(l1) + 1))
X#define Hmax(m,l1) ((l1) - (m))
X#define size(m,sm,l1) (((l1) - (m)) - (sm))
X#define limitm1(l1) (l1)
X#define ipos2pos(n,ip,l1) ((l1) - (ip))
X#define pos2ipos(n,po,l1) ((l1) - (po))
X
X#ifdef PTRS
X#define node2pos(n,no,l1) ((l1) - ((no) - (n)))
X#define node2ipos(n,no,l1) ((no) - (n))
X#else
X#define node2pos(n,no,l1) ((l1) - (no))
X#define node2ipos(n,no,l1) (no)
X#endif
X
X#define ipos2node(n,ip,l1) (NODEBYN(n,ip))
X#define pos2node(n,po,l1) (NODEBYN(n,(l1) - (po)))
X
X#endif
END_OF_FILE
  if test 7295 -ne `wc -c <'huptrie.h'`; then
    echo shar: \"'huptrie.h'\" unpacked with wrong size!
  fi
  # end of 'huptrie.h'
fi
if test -f 'percent.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'percent.c'\"
else
  echo shar: Extracting \"'percent.c'\" \(2070 characters\)
  sed "s/^X//" >'percent.c' <<'END_OF_FILE'
X/* Placed into the public domain by Daniel J. Bernstein. */
X
X#include "percent.h"
X
X#define MAXULONG ((unsigned long) (-1))
X
X#define HENCE(x) ;
X
X#define ENOUGH(a) { long p = (a); if (q) { \
Xif (q - 1 > limit / 100) return limit; \
Xif ((q - 1) * 100 > limit - 100) return limit; \
Xif (q * 100 > limit - p) return limit; \
Xreturn (long) (p + q*100); } else if (p > limit) return limit; else return p; }
X
Xlong percent(a,b,limit)
Xunsigned long a;
Xunsigned long b;
Xlong limit;
X{
X unsigned long q;
X unsigned long s;
X unsigned long t;
X
X q = 0;
X
X if (b == 0)
X   ENOUGH(100)
X HENCE(b > 0);
X
X if (b < MAXULONG - 200)
X   if (a < (MAXULONG / 200) - (b / 200) - 1) /* cannot go below 0 */
X     ENOUGH((100 * a + (b / 2)) / b) /* cannot overflow */
X HENCE(a + (b / 200) + 1 >= MAXULONG / 200);
X /* How often will a and b be more than 21 million on a 32-bit machine? */
X
X if (a < b / 200)
X   ENOUGH(0)
X HENCE(a >= b / 200);
X HENCE(a + a + 1 >= MAXULONG / 200);
X
X if (a >= b)
X  {
X   q = a / b;
X   HENCE(a - q * b < b);
X   a -= q * b;
X  }
X HENCE(a < b);
X
X t = 0; s = a;
X /* now s is a mod b, t is floor(a/b) */
X if (s >= b - a) { t += 1; s -= b - a; } else { s += a; }
X /* now s is 2a mod b, t is floor(2a/b) */
X if (s >= b - a) { t += 1; s -= b - a; } else { s += a; }
X /* now s is 3a mod b, t is floor(3a/b) */
X if (s >= b - s) { t += t + 1; s -= b - s; } else { t += t; s += s; }
X /* now s is 6a mod b, t is floor(6a/b) */
X if (s >= b - s) { t += t + 1; s -= b - s; } else { t += t; s += s; }
X /* now s is 12a mod b, t is floor(12a/b) */
X if (s >= b - s) { t += t + 1; s -= b - s; } else { t += t; s += s; }
X /* now s is 24a mod b, t is floor(24a/b) */
X if (s >= b - a) { t += 1; s -= b - a; } else { s += a; }
X /* now s is 25a mod b, t is floor(25a/b) */
X if (s >= b - s) { t += t + 1; s -= b - s; } else { t += t; s += s; }
X /* now s is 50a mod b, t is floor(50a/b) */
X if (s >= b - s) { t += t + 1; s -= b - s; } else { t += t; s += s; }
X /* now s is 100a mod b, t is floor(100a/b) */
X if (s >= b - (b/2)) { t += 1; s -= b - (b/2); } else { s += (b/2); }
X
X ENOUGH(t)
X /* whew. */
X}
END_OF_FILE
  if test 2070 -ne `wc -c <'percent.c'`; then
    echo shar: \"'percent.c'\" unpacked with wrong size!
  fi
  # end of 'percent.c'
fi
if test -f 'sysconf' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'sysconf'\"
else
  echo shar: Extracting \"'sysconf'\" \(4852 characters\)
  sed "s/^X//" >'sysconf' <<'END_OF_FILE'
X#!/bin/sh
X# Public domain.
X
X# Configure, eat your heart out.
X
X# make sure we're using sh (stolen from Configure)
XPATH='.:/bin:/usr/bin:/usr/local/bin:/usr/ucb:/usr/local:/usr/lbin:/etc'
Xexport PATH || (echo "Aargh! This isn't sh. Desperation time. I will now feed myself to sh..."; exec sh $0; sh $0; kill $$)
Xecho "We're using sh. Good."
X
X# make sure cmp works
Xif cmp README README >/dev/null 2>&1
Xthen if cmp README FORMLETTER >/dev/null 2>&1
X     then echo 'Aargh! cmp returns a zero exit code for different files. This is hopeless.'
X      exit 1
X     else echo 'You have a normal cmp. Good.'
X     fi
Xelse echo 'Aargh! cmp returns a nonzero exit code for the same file. This is hopeless.'
X     exit 1
Xfi
X
X# test for bzero()
Xcat > .bzero.$$.c << 'YOW'
Xextern bzero(); main() { char c = 1; bzero(&c,1); printf("%d\n",c); }
XYOW
Xif cc -o .bzero.$$ .bzero.$$.c >/dev/null 2>&1
Xthen ./.bzero.$$ > .bzero.$$.out
X     echo 0 > .zero.$$.out
X     if cmp .zero.$$.out .bzero.$$.out >/dev/null 2>&1
X     then echo 'You have bzero(). Enabling it...'
X      sed '2s/$/ -DBZERO/' < Makefile | sed '2s/-UBZERO /-DBZERO /g' | sed '2s/-DBZERO\(.*\) -DBZERO$/-DBZERO\1/' > Makefile.new
X      mv Makefile.new Makefile
X     else echo 'You seem to have bzero(), but it doesn'\''t work. Disabling it...'
X      sed '2s/$/ -UBZERO/' < Makefile | sed '2s/-DBZERO /-UBZERO /g' | sed '2s/-UBZERO\(.*\) -UBZERO$/-UBZERO\1/' > Makefile.new
X      mv Makefile.new Makefile
X     fi
Xelse echo 'You do not have bzero(). Disabling it...'
X     sed '2s/$/ -UBZERO/' < Makefile | sed '2s/-DBZERO /-UBZERO /g' | sed '2s/-UBZERO\(.*\) -UBZERO$/-UBZERO\1/' > Makefile.new
X     mv Makefile.new Makefile
Xfi
Xrm -f .bzero.$$ .bzero.$$.out .bzero.$$.c .zero.$$.out
X
X# test for memset()
Xcat > .mmset.$$.c << 'YOW'
Xextern memset(); main() { char c = 1; memset(&c,0,1); printf("%d\n",c); }
XYOW
Xif cc -o .mmset.$$ .mmset.$$.c >/dev/null 2>&1
Xthen ./.mmset.$$ > .mmset.$$.out
X     echo 0 > .zero.$$.out
X     if cmp .zero.$$.out .mmset.$$.out >/dev/null 2>&1
X     then echo 'You have memset(). Enabling it...'
X      sed '2s/$/ -DMEMZERO/' < Makefile | sed '2s/-UMEMZERO /-DMEMZERO /g' | sed '2s/-DMEMZERO\(.*\) -DMEMZERO$/-DMEMZERO\1/' > Makefile.new
X      mv Makefile.new Makefile
X     else echo 'You seem to have memset(), but it doesn'\''t work. Disabling it...'
X      sed '2s/$/ -UMEMZERO/' < Makefile | sed '2s/-DMEMZERO /-UMEMZERO /g' | sed '2s/-UMEMZERO\(.*\) -UMEMZERO$/-UMEMZERO\1/' > Makefile.new
X      mv Makefile.new Makefile
X     fi
Xelse echo 'You do not have memset(). Disabling it...'
X     sed '2s/$/ -UMEMZERO/' < Makefile | sed '2s/-DMEMZERO /-UMEMZERO /g' | sed '2s/-UMEMZERO\(.*\) -UMEMZERO$/-UMEMZERO\1/' > Makefile.new
X     mv Makefile.new Makefile
Xfi
Xrm -f .mmset.$$ .mmset.$$.out .mmset.$$.c .zero.$$.out
X
X# test for putchar not sign-extending correctly
Xcat > .bozo.$$.c << 'YOW'
X#include <stdio.h>
Xmain() { int i=255; putchar(25); exit(putchar((char)i) != EOF); }
XYOW
Xif cc -o .bozo.$$ .bozo.$$.c >/dev/null 2>&1
Xthen if ./.bozo.$$ >/dev/null
X     then echo 'You have the putchar((char) 255) == EOF bug.'
X      echo 'Let me put -DBRAINDAMAGED into the Makefile for you...'
X      sed '2s/$/ -DBRAINDAMAGED/' < Makefile | sed '2s/-UBRAINDAMAGED /-DBRAINDAMAGED /g' | sed '2s/-DBRAINDAMAGED\(.*\) -DBRAINDAMAGED$/-DBRAINDAMAGED\1/' > Makefile.new
X      mv Makefile.new Makefile
X      echo 'You *must* make sure to leave this defined.'
X     else echo 'You do not have the putchar((char) 255) == EOF bug.'
X      echo 'Making sure -DBRAINDAMAGED is not in the Makefile...'
X      sed '2s/$/ -UBRAINDAMAGED/' < Makefile | sed '2s/-DBRAINDAMAGED /-UBRAINDAMAGED /g' | sed '2s/-UBRAINDAMAGED\(.*\) -UBRAINDAMAGED$/-UBRAINDAMAGED\1/' > Makefile.new
X      mv Makefile.new Makefile
X     fi
Xelse echo 'Weird, cannot compile normal stdio program.'
X     echo 'Making sure -DBRAINDAMAGED is not in the Makefile...'
X     sed '2s/$/ -UBRAINDAMAGED/' < Makefile | sed '2s/-DBRAINDAMAGED /-UBRAINDAMAGED /g' | sed '2s/-UBRAINDAMAGED\(.*\) -UBRAINDAMAGED$/-UBRAINDAMAGED\1/' > Makefile.new
X     mv Makefile.new Makefile
Xfi
Xrm -f .bozo.$$ .bozo.$$.out .bozo.$$.c .zero.$$.out
X
X# set ZEROFILLED
Xecho "Since you're running this script, I assume that you're on a UNIX machine,"
Xecho "and static arrays are zero-filled by default. Enabling -DZEROFILLED..."
Xsed '2s/$/ -DZEROFILLED/' < Makefile | sed '2s/-UZEROFILLED /-DZEROFILLED /g' | sed '2s/-DZEROFILLED\(.*\) -DZEROFILLED$/-DZEROFILLED\1/' > Makefile.new
Xmv Makefile.new Makefile
X
Xecho ' '
Xecho 'Okay, now you should make checkconf and run it.'
Xecho 'If you would like me to do this for you, press return.'
Xecho 'Otherwise type no and press return, or just interrupt this script.'
Xread foo
Xcase x"$foo"y in
Xxy) echo 'make checkconf'
X    if make checkconf
X    then echo './checkconf'
X     ./checkconf
X    else echo 'Oops, make checkconf failed. I give up: you figure it out.'
X    fi
X    ;;
Xesac
X
Xexit 0
END_OF_FILE
  if test 4852 -ne `wc -c <'sysconf'`; then
    echo shar: \"'sysconf'\" unpacked with wrong size!
  fi
  chmod +x 'sysconf'
  # end of 'sysconf'
fi
if test -f 'texts.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'texts.c'\"
else
  echo shar: Extracting \"'texts.c'\" \(6240 characters\)
  sed "s/^X//" >'texts.c' <<'END_OF_FILE'
X/* Placed into the public domain by Daniel J. Bernstein. */
X
X/* If you change the code, you should (1) add your name to sqauthor[] */
X/* and/or unsqauthor[]; (2) add a patch label to the version numbers */
X/* in sqversion[], sqcopyright[], unsqversion[], and unsqcopyright[]; */
X/* (3) change squsage[], sqhelp[], unsqusage[], and unsqhelp[] if you */
X/* changed the interface. The patch label should be a slash, your */
X/* initials, and the date the patch was released---e.g., version */
X/* 0.98 might become 0.98/JS032291 and then 0.98/JS032291/SS040591. */
X/* If you let me know about your changes, I'll try to integrate them */
X/* into the next release. */
X
X#include "texts.h"
X
Xchar *sqauthor[] = {
X"yabbawhap was written by Daniel J. Bernstein." ,
X"Internet address: [e-mail]." ,
X0 } ;
X
Xchar *sqversion[] = {
X"yabbawhap version 1.00, March 19, 1991." ,
X"Placed into the public domain by Daniel J. Bernstein." ,
X0 } ;
X
Xchar *sqcopyright[] = {
X"yabbawhap version 1.00, March 19, 1991." ,
X"Placed into the public domain by Daniel J. Bernstein." ,
X"" ,
X"There is no copyright on this code. You may use it in any way you want." ,
X"" ,
X"If you have questions about this program or about this notice, or if you" ,
X"have a patch that you don't mind sharing, please contact me on the Internet" ,
X"at [e-mail]." ,
X0 } ;
X
Xchar *sqwarranty[] = {
X"Daniel J. Bernstein disclaims all warranties to the extent permitted" ,
X"by applicable law. He is not and shall not be liable for any damages" ,
X"arising from the use of this program. This disclaimer shall be governed" ,
X"by the laws of the state of New York." ,
X"" ,
X"In other words, use this program at your own risk." ,
X"" ,
X"If you have questions about this program or about this disclaimer of" ,
X"warranty, please feel free to contact me at [e-mail] on the" ,
X"Internet." ,
X0 } ;
X
Xchar *squsage[] = {
X#ifdef WHAP
X"Usage: whap [ -mmem ] [ -znum ] [ -Zfuzz ] [ -qQv^rRACHUVW ]" ,
X"Help:  whap -H" ,
X#else
X"Usage: yabba [ -mmem ] [ -znum ] [ -Zfuzz ] [ -qQv^rRACHUVW ]" ,
X"Help:  yabba -H" ,
X#endif
X0 } ;
X
Xchar *sqhelp[] = {
X#ifdef WHAP
X"whap compresses its input using AP coding. It writes the result to its output." ,
X"whap -ACHUVW: print authorship notice, copyright notice, this notice," ,
X"              short usage summary, version number, disclaimer of warranty" ,
X"whap [ -mmem ] [ -znum ] [ -Zfuzz ] [ -qQv^rR ]: compress" ,
X#else
X"yabba compresses its input using Y coding. It writes the result to its output." ,
X"yabba -ACHUVW: print authorship notice, copyright notice, this notice," ,
X"               short usage summary, version number, disclaimer of warranty" ,
X"yabba [ -mmem ] [ -znum ] [ -Zfuzz ] [ -qQv^rR ]: compress" ,
X#endif
X"-mmem: set block size to mem (default: factory 65533 chars, here %d)" ,
X"-r: randomize output to prepare for encryption; also omit header" ,
X"-R: don't randomize (default); use header" ,
X"-q: quiet (nothing on standard error)" ,
X"-Q: normal level of verbosity" ,
X"-v: verbose: like  In: 312163 chars  Out: 106253 chars  Whapped to: 34%%" ,
X"-znum: set blocking test length (factory default 8192)" ,
X"-Zfuzz: set blocking fuzz (factory default 30)" ,
X"-^: like -v, but print percent saved rather than percent remaining" ,
X"" ,
X#ifdef WHAP
X"unwhap must be given the same settings of -m and -r/-R." ,
X#else
X"unyabba must be given the same settings of -m and -r/-R." ,
X#endif
X"" ,
X"If you have questions about or suggestions for yabbawhap, please feel free" ,
X"to contact the author, Daniel J. Bernstein, at [e-mail] on the" ,
X"Internet." ,
X0 } ;
X
Xchar *unsqauthor[] = {
X"yabbawhap was written by Daniel J. Bernstein." ,
X"Internet address: [e-mail]." ,
X0 } ;
X
Xchar *unsqversion[] = {
X"yabbawhap version 1.00, March 19, 1991." ,
X"Placed into the public domain by Daniel J. Bernstein." ,
X0 } ;
X
Xchar *unsqcopyright[] = {
X"yabbawhap version 1.00, March 19, 1991." ,
X"Placed into the public domain by Daniel J. Bernstein." ,
X"" ,
X"There is no copyright on this code. You may use it in any way you want." ,
X"" ,
X"If you have questions about this program or about this notice, or if you" ,
X"have a patch that you don't mind sharing, please contact me on the Internet" ,
X"at [e-mail]." ,
X0 } ;
X
Xchar *unsqwarranty[] = {
X"Daniel J. Bernstein disclaims all warranties to the extent permitted" ,
X"by applicable law. He is not and shall not be liable for any damages" ,
X"arising from the use of this program. This disclaimer shall be governed" ,
X"by the laws of the state of New York." ,
X"" ,
X"In other words, use this program at your own risk." ,
X"" ,
X"If you have questions about this program or about this disclaimer of" ,
X"warranty, please feel free to contact me at [e-mail] on the" ,
X"Internet." ,
X0 } ;
X
Xchar *unsqusage[] = {
X#ifdef WHAP
X"Usage: unwhap [ -mmem ] [ -qQvrRACHUVW ]" ,
X"Help:  unwhap -H" ,
X#else
X"Usage: unyabba [ -mmem ] [ -qQvrRACHUVW ]" ,
X"Help:  unyabba -H" ,
X#endif
X0 } ;
X
Xchar *unsqhelp[] = {
X#ifdef WHAP
X"unwhap uncompresses its input, which must have come from whap, to its output." ,
X"unwhap -ACHUVW: print authorship notice, copyright notice, this notice," ,
X"                short usage summary, version number, disclaimer of warranty" ,
X"unwhap [ -mmem ] [ -qQvrR ]: uncompress" ,
X#else
X"unyabba uncompresses its input, which must have come from yabba, to its output." ,
X"unyabba -ACHUVW: print authorship notice, copyright notice, this notice," ,
X"                 short usage summary, version number, disclaimer of warranty" ,
X"unyabba [ -mmem ] [ -qQvrR ]: uncompress" ,
X#endif
X"-mmem: set block size to mem (default: factory 65533 chars, here %d)" ,
X"-r: accept randomized input without a header" ,
X"-R: complain about randomized input; check for header" ,
X"-q: quiet (nothing on standard error)" ,
X"-Q: normal level of verbosity" ,
X"-v: verbose: like  In: 106253 chars  Out: 312163 chars  Whapped from: 34%%" ,
X"" ,
X#ifdef WHAP
X"The whap that wrote the input must have the same settings of -m and -r/-R." ,
X#else
X"The yabba that wrote the input must have the same settings of -m and -r/-R." ,
X#endif
X"" ,
X"If you have questions about or suggestions for yabbawhap, please feel free" ,
X"to contact the author, Daniel J. Bernstein, at [e-mail] on the" ,
X"Internet." ,
X0 } ;
END_OF_FILE
  if test 6240 -ne `wc -c <'texts.c'`; then
    echo shar: \"'texts.c'\" unpacked with wrong size!
  fi
  # end of 'texts.c'
fi
if test -f 'unwhap.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'unwhap.c'\"
else
  echo shar: Extracting \"'unwhap.c'\" \(6299 characters\)
  sed "s/^X//" >'unwhap.c' <<'END_OF_FILE'
X/* Placed into the public domain by Daniel J. Bernstein. */
X
Xstatic char whapwarning[] = "\
XWARNING! If you use AP coding except for instruction and amusement,\n\
Xyou may be infringing upon a patent.\n\
X";
X
X#include <stdio.h>
Xextern long atol();
Xextern int getopt();
Xextern char *optarg;
Xextern int optind;
X#include "percent.h"
X#include "texts.h"
X
Xstatic char progname[] = "unwhap";
Xstatic char progged[] = "Unwhapped";
X
X#ifndef TYPE
X#define TYPE short
X#endif
X
Xtypedef TYPE bitnum;
Xtypedef unsigned TYPE bitword;
X
Xint twom1[9] = { 0,1,3,7,15,31,63,127,255 } ;
X
X#ifndef NODEMAX
X#define NODEMAX (65533)
X#endif
X#ifndef NODENUM
X#define NODENUM NODEMAX
X#endif
Xstatic char outarray[NODEMAX]; /* first 256 spots unused, boo hoo hoo */
Xstatic bitword outstart[NODEMAX]; /* first 256 spots unused, boo hoo hoo */
X
X#define MAXPLUS max++; oamax++; osmax++; \
Xif (max == nextbits) { bits++; nextbits <<= 1; }
X
Xstatic unsigned long savein;
Xstatic unsigned long saveout;
Xstatic int flagverbose = 1;
Xstatic int flagrandom = 0;
X
Xvoid goaheadandbeverbose()
X{
X long per = percent(savein,saveout,10000L);
X
X if (per == 10000L) /* absolutely ridiculous */
X   fprintf(stderr,"In: %ld chars  Out: %ld chars  %s from: >9999%%\n",
X           savein,saveout,progged);
X else
X   fprintf(stderr,"In: %ld chars  Out: %ld chars  %s from: %ld%%\n",
X       savein,saveout,progged,per);
X}
X
Xvoid fatalinfo(x,s)
Xint x;
Xchar **s;
X{
X if (flagverbose) while (*s)
X  {
X   fprintf(stderr,*(s++),NODENUM);
X   putc('\n',stderr);
X  }
X (void) exit(x);
X}
X
X#define PUTERR { if (flagverbose) fprintf(stderr,"%s: fatal: output error\n",progname); \
Xsavein = in; saveout = out; \
Xif (flagverbose >= 2) goaheadandbeverbose(); (void) exit(2); }
X
Xmain(argc,argv)
Xint argc;
Xchar *argv[];
X{
X register bitword i;
X register char *j;
X register bitword outb;
X register bitword max;
X register bitword nextbits;
X register bitnum bits;
X register bitword curw = 0;
X register bitnum curbb = 0;
X register int ch;
X register char *oamax;
X register bitword *osmax;
X register char *oai;
X register bitword min = NODENUM - 1; /* maximum decompressor size - 1 */
X register unsigned long in = 0;
X register unsigned long out = 0;
X
X  {
X   int opt;
X   bitword i;
X
X   while ((opt = getopt(argc,argv,"m:vqQrRACHUVW")) != EOF)
X     switch(opt)
X      {
X       case '?': fatalinfo(1,unsqusage);
X       case 'm': i = atol(optarg);
X         if ((i < 512) || (i > NODEMAX))
X          {
X           if (flagverbose) fprintf(stderr,
X              "%s: fatal: mem size out of range: must be between 512 and %ld\n",
X              progname,(long) NODEMAX);
X           (void) exit(1);
X          }
X         min = i - 1;
X         break;
X       case 'v': flagverbose = 2; break;
X       case 'q': flagverbose = 0; break;
X       case 'Q': flagverbose = 1; break;
X       case 'r': flagrandom = 1; break;
X       case 'R': flagrandom = 0; break;
X       case 'A': fatalinfo(1,unsqauthor); break;
X       case 'C': fatalinfo(1,unsqcopyright); break;
X       case 'H': fatalinfo(1,unsqhelp); break;
X       case 'U': fatalinfo(1,unsqusage); break;
X       case 'V': fatalinfo(1,unsqversion); break;
X       case 'W': fatalinfo(1,unsqwarranty); break;
X      }
X   argv += optind;
X   argc -= optind;
X  }
X
X if (flagverbose)
X   fprintf(stderr,whapwarning);
X
X if (!flagrandom)
X  {
X   bitword i = 0;
X   int r;
X
X   if ((getchar() != 23)
X     ||(getchar() != 8)
X     ||(getchar() != 1)
X     ||(getchar() != 16)
X     ||((r = getchar()) == EOF))
X    {
X     if (flagverbose) fprintf(stderr,"%s: fatal: input not in right format\n",progname);
X     (void) exit(3);
X    }
X   in += 5;
X   while (r)
X    {
X     if (((ch = getchar()) == EOF) || (ch < 48) || (ch > 57))
X      {
X       if (flagverbose) fprintf(stderr,"%s: fatal: input not in right format\n",progname);
X       (void) exit(3);
X      }
X     ++in;
X     i = i * 10 + (ch - 48);
X     --r;
X    }
X   if (i != min + 1)
X    {
X     if (flagverbose) fprintf(stderr,"%s: fatal: input has -m %ld, I have -m %ld\n"
X         ,progname,(long) i,(long) (min + 1));
X     (void) exit(4);
X    }
X  }
X
X#define MINIT max = 256; oamax = outarray + 256; osmax = outstart + 256; \
Xoutb = 256; nextbits = 256; bits = 8; \
Xwhile (max >= nextbits) { bits++; nextbits <<= 1; }
X/* of course, max = 255 plus one for table clearing */
X
X MINIT
X
X for (;;)
X  {
X   /* assumes bits >= 8 */
X   while (curbb + 8 < bits) /* could be an if, when bits is < 16 */
X     if ((ch = getchar()) != EOF)
X      {
X       curw += ch << curbb;
X       curbb += 8;
X       ++in; /* XXX: check for overflow */
X      }
X     else
X      {
X       savein = in; saveout = out;
X       if (flagverbose >= 2)
X     goaheadandbeverbose();
X       (void) exit(0);
X      }
X   if ((ch = getchar()) == EOF)
X    {
X     savein = in; saveout = out;
X     if (flagverbose >= 2)
X       goaheadandbeverbose();
X     (void) exit(0);
X    }
X   i = curw + ((ch & twom1[bits - curbb]) << curbb);
X   curw = ch >> (bits - curbb);
X   curbb = 8 - (bits - curbb);
X   ++in; /* XXX: check for overflow */
X
X   /* XXX: flagpedantic to control whether we make this test? */
X   if (i > max)
X     if (flagrandom)
X       i -= max + 1;
X     else
X      {
X       if (flagverbose) fprintf(stderr,"%s: fatal: input corrupt at byte %ld\n",progname,in);
X       (void) exit(5);
X      }
X
X   if (i < 257) /* 256 is special */
X     if (i != 256)
X      {
X       if (max != min)
X    {
X         MAXPLUS
X     *osmax = outb;
X     *oamax = i;
X         outb = max;
X    }
X#ifdef BRAINDAMAGED
X       if (i == 255)
X     putchar((char) i);
X       else
X#endif
X       if (putchar((char) i) == EOF)
X         PUTERR
X       ++out; /* XXX: check for overflow */
X      }
X     else
X      {
X       /* here's where blocking stuff should go */
X       MINIT
X       /* wow, that was easy */
X      }
X   else
X    {
X     oai = outarray + i;
X     j = outarray + outstart[i] - 1;
X     while ((j != oai) && (max != min))
X      {
X       MAXPLUS
X       *oamax = *++j;
X#ifdef BRAINDAMAGED
X       if (*oamax == (char) 255)
X     putchar(*oamax);
X       else
X#endif
X       if (putchar(*oamax) == EOF)
X     PUTERR
X       ++out; /* XXX: check for overflow */
X       *osmax = outb;
X      }
X     while (j != oai)
X      {
X       ++j;
X#ifdef BRAINDAMAGED
X       if (*j == (char) 255)
X     putchar(*j);
X       else
X#endif
X       if (putchar(*j) == EOF)
X     PUTERR
X       ++out; /* XXX: check for overflow */
X      }
X     outb = max - (i - outstart[i]);
X    }
X#ifdef notdef
X/*XXX: -d code */
X#endif
X  }
X}
END_OF_FILE
  if test 6299 -ne `wc -c <'unwhap.c'`; then
    echo shar: \"'unwhap.c'\" unpacked with wrong size!
  fi
  # end of 'unwhap.c'
fi
if test -f 'unyabba.1' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'unyabba.1'\"
else
  echo shar: Extracting \"'unyabba.1'\" \(2906 characters\)
  sed "s/^X//" >'unyabba.1' <<'END_OF_FILE'
X.TH unyabba 1
X.SH NAME
Xunyabba \- decompress data compressed with Y coding
X
Xunwhap \- decompress data compressed with AP coding
X.SH SYNTAX
Xunyabba
X[
X\fB\-m\fImem
X] [
X\fB\-qQvrR\fI
X] [
X\fB\-ACHUVW\fI
X]
X
X\fBunwhap
X[
X\fB\-m\fImem
X] [
X\fB\-qQvrR\fI
X] [
X\fB\-ACHUVW\fI
X]
X.SH DESCRIPTION
X.I unyabba
Xdecompresses its standard input,
Xwhich must have come from
X.I yabba,
Xand writes the result to its standard output.
X
X.I unwhap
Xis like
X.I unyabba,
Xbut works with files from
X.I whap.
XWarning: If you use
X.I unwhap
Xexcept for experimental use,
Xyou may be infringing upon a patent.
X
XOptions
X.B ACHUVW
Xprint the authorship notice,
Xcopyright notice,
Xhelp notice,
Xshort usage summary,
Xversion number,
Xand warranty information respectively.
X
X.I unyabba
Xhas several flags:
X.TP 12
X.B\-m\fImem
XAssume that the input was produced for memory size
X.I mem.
X.I yabba
Xmust have been given the same value of
X.I mem.
X.I mem
Xcannot be larger than a value specified at compile-time.
XTypical values of
X.I mem
Xare 12000, 20000, 40000, 65533, 200000, 500000, and 1000000.
X.TP
X.B\-r
XAssume that the input was ``randomized''
Xby
X.I yabba.
X.I unyabba
Xwill not expect its usual header,
Xand will strip out the pseudo-random information
Xintroduced by
X.I yabba.
XCaveat:
X.I unyabba
Xnormally checks for the proper
X.B\-m
Xsetting in the input.
XUnder
X.B\-r,
Xit cannot do so.
X.TP
X.B\-R
XLook for the usual header, and complain about apparently random input.
XThis is the default.
X.TP
X.B\-v
X.I unyabba
Xwill be ``verbose'' and report compression statistics
Xto standard error.
X.TP
X.B\-q
XQuiet.
X.I unyabba
Xwill not use
Xstandard error in any way.
X.TP
X.B\-Q
XNormal level of verbosity.
X.PP
X.B\-m,
X.B\-r,
Xand
X.B\-R
Xassume a different structure for the compressed file.
XBe careful to have selected the same flags for
X.I yabba.
X.SH DIAGNOSTICS
X.TP
X\fIIn:\fB xxx \fIchars  Out:\fB xxx \fIchars  UnY'd from:\fB xx%
XThe utilizer of the computational machinery
Xhas specified the ``verbose'' option
Xto
X.I unyabba
Xvia the
Xestablishment of the character v
Xwithin an argument
Xpreceded by a hyphen.
X.TP
X\fIfatal: output error\fB
XSelf-explanatory.
X.TP
X\fIfatal: input not in right format\fB
XThe
X.I yabba
Xheader is not there.
X.TP
X\fIfatal: input has \-m xxx, I have \-m yyy\fB
XSelf-explanatory.
X.TP
X\fIfatal: input corrupt
XThe input is not a compressed file. (Note that
X.I unyabba
Xwill always detect this, unlike
X.I uncompress,
Xwhich may simply produce incorrect output.)
XDid you compress with
X.B\-r?
X.SH "EXIT CODE"
X0 normally, 1 for syntax errors or usage messages,
X2 for output errors,
X3 if the input is not in the right format,
X4 if the input was compressed with a different value of
X.I mem,
X5 if the input is corrupt.
X.SH FILES
XNone.
X.SH BUGS
XNone known.
X.SH VERSION
Xunwhap 1.00, March 19, 1991.
X.SH AUTHOR
XPlaced into the public domain by Daniel J. Bernstein.
X.SH REFERENCES
XD. J. Bernstein, ``Y coding.''
XPreprints available soon.
X.SH "SEE ALSO"
Xyabba(1),
Xcompress(1)
END_OF_FILE
  if test 2906 -ne `wc -c <'unyabba.1'`; then
    echo shar: \"'unyabba.1'\" unpacked with wrong size!
  fi
  # end of 'unyabba.1'
fi
if test -f 'yabba.1' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'yabba.1'\"
else
  echo shar: Extracting \"'yabba.1'\" \(3586 characters\)
  sed "s/^X//" >'yabba.1' <<'END_OF_FILE'
X.TH yabba 1
X.SH NAME
Xyabba \- compress data with Y coding
X
Xwhap \- compress data with AP coding
X.SH SYNTAX
Xyabba
X[
X\fB\-m\fImem
X] [
X\fB\-z\fInum
X] [
X\fB\-Z\fIfuzz
X] [
X\fB\-qQv^rR\fI
X] [
X\fB\-ACHUVW\fI
X]
X
X\fBwhap
X[
X\fB\-m\fImem
X] [
X\fB\-z\fInum
X] [
X\fB\-Z\fIfuzz
X] [
X\fB\-qQv^rR\fI
X] [
X\fB\-ACHUVW\fI
X]
X.SH DESCRIPTION
X.I yabba
Xcompresses its standard input
Xand writes the result to its standard output.
X\fIyabba\fBd
Xfiles can be restored
Xwith
X\fIunyabba\fB.
X
X.I whap
Xis like
X.I yabba,
Xbut uses AP coding.
XWarning: If you use
X.I whap
Xexcept for experimental use,
Xyou may be infringing upon a patent.
X
XOptions
X.B ACHUVW
Xprint the authorship notice,
Xcopyright notice,
Xhelp notice,
Xshort usage summary,
Xversion number,
Xand warranty information respectively.
X
X.I yabba
Xhas several flags:
X.TP 12
X.B\-m\fImem
XProduce output for memory size
X.I mem.
X.I unyabba
Xmust be given the same value of
X.I mem.
X.I mem
Xcannot be larger than a value specified at compile-time;
Xif you compress with a
X.I mem
Xlarger than the maximum value for the
Xtarget
X.I unyabba,
Xyou will not be able to decompress the file.
XTypical values of
X.I mem
Xare 12000, 20000, 40000, 65533, 200000, 500000, and 1000000.
X.TP
X.B\-r
XProduce ``randomized'' output suitable for encryption.
X.I yabba
Xwill introduce
Xpseudo-random bits of information
Xinto the output, and will leave off its usual output header.
XNormally, for efficiency and so that
X.I yabba
Xcan produce output before seeing the end of the input,
Xcompressed texts must have some slight output redundancy.
XUnder
X.B\-r,
Xmost of this redundancy disappears
Xand almost all
X\fIY'\fBd
Xtexts are possible.
XCaveat: the beginning
Xof the output depends only
Xon the beginning
Xof the input,
Xso you should make sure
Xto
X.I precede the uncompressed input
X.I by unpredictable data
Xbefore feeding it to
X.I yabba.
X.TP
X.B\-R
XDo not randomize output, and include the usual header.
XThis is the default.
X.TP
X.B\-Z\fIfuzz
X.I yabba
Xmaintains a
X``dictionary''
Xof strings
Xadapted to the data seen so far.
XWhen
X.I yabba
Xruns out of memory (as specified by
X.B\-m),
Xit will periodically test whether the compression ratio is
Xgood enough.
XIf not, it will adapt to the next ``block''
Xof the file
Xby throwing out the dictionary and starting over.
X.I fuzz
Xhas some vaguely defined effect
Xon what ``good enough'' means;
Xthe higher
X.I fuzz
Xis, the longer
X.I yabba
Xwill hold out before clearing the dictionary.
X.I fuzz
Xis 30 by default.
X.TP
X.B\-z\fInum
X.I num
Xsets how often
X.I yabba
Xwill check for clearing the dictionary.
XThe default is every 8192 characters.
X.TP
X.B\-v
X.I yabba
Xwill be ``verbose'' and report compression statistics
Xto standard error.
X.TP
X.B\-^
XSame as
X.B\-v,
Xbut reports the percent saved rather than the percent left.
X.TP
X.B\-q
XQuiet.
X.I yabba
Xwill not use
Xstandard error in any way.
X.TP
X.B\-Q
XNormal level of verbosity.
X.PP
X.B\-m,
X.B\-r,
Xand
X.B\-R
Xchange the structure of the compressed file.
XBe careful to select the same flags for
X.I unyabba.
X.SH DIAGNOSTICS
X.TP
X\fIIn:\fB xxx \fIchars  Out:\fB xxx \fIchars  Y'd to:\fB xx%
XThe utilizer of the computational machinery
Xhas specified the ``verbose'' option
Xto
X.I yabba
Xvia the
Xestablishment of the character v
Xwithin an argument
Xpreceded by a hyphen.
X.TP
X\fIfatal: output error\fB
XSelf-explanatory.
X.SH "EXIT CODE"
X0 normally, 1 for syntax errors or usage notices,
X2 for output errors.
X.SH FILES
XNone.
X.SH BUGS
XNone known.
X.SH VERSION
Xyabba 1.00, March 19, 1991.
X.SH AUTHOR
XPlaced into the public domain by Daniel J. Bernstein.
X.SH REFERENCES
XD. J. Bernstein, ``Y coding.''
XPreprints available soon.
X.SH "SEE ALSO"
Xunyabba(1),
Xcompress(1)
END_OF_FILE
  if test 3586 -ne `wc -c <'yabba.1'`; then
    echo shar: \"'yabba.1'\" unpacked with wrong size!
  fi
  # end of 'yabba.1'
fi
echo shar: End of archive 3 \(of 4\).
cp /dev/null ark3isdone
MISSING=""
for I in 1 2 3 4 ; do
    if test ! -f ark${I}isdone ; then
    MISSING="${MISSING} ${I}"
    fi
done
if test "${MISSING}" = "" ; then
    echo You have unpacked all 4 archives.
    rm -f ark[1-9]isdone
else
    echo You still must unpack the following archives:
    echo "        " ${MISSING}
fi
exit 0
exit 0 # Just in case...